Codeforces Round 506 (Div. 3)

Posted on | In ,

补题进度：Done
我的人生也就做做水题维持维持生活了
$pb-ds$库是个神奇的东西啊

题目链接

A,B

签到

C

很显然枚举每个删除的线段，取左端点的max，右端点的min比较一下就好了

D

题意

给n个数，每个数可以其他的数拼接一起(显然一共有$n·(n-1)$种搭配)，问其中可以被 $k$ 整除的方案数

题解

  • 直接开是10个map(__gnu_pbds::cc_hash_table)，记录每个数作为前缀的情况
  • 然后枚举每个数作为后缀的情况即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
#define ll unsigned long long
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;

const int maxn=2e5+7;

__gnu_pbds::cc_hash_table<ll, ll> mp[11];
int n, k;
ll a[maxn], ans;
ll fac[13];

int main()
{
    fac[0]=1;
    for(int i=1;i<=10;i++)
        fac[i]=10LL*fac[i-1];
    scanf("%d%d", &n, &k);
    for(int i=1;i<=n;i++)
    {
        scanf("%llu", &a[i]);
        for(int j=1;j<=10;j++)
        {
            int now=(a[i]*fac[j])%k;
            mp[j][now]++;
        }
    }
    for(int i=1;i<=n;i++){
        int len=0;
        ll now=a[i];
        while(now){
            now/=10;
            len++;
        }
        int res=a[i]%k;
        if(res!=0) res=k-res;
        ans+=mp[len][res];
        if((a[i] + a[i]*fac[len])%k == 0)
            ans--;
    }
    printf("%lld\n", ans);
    return 0;
}

E

题意

给一颗n个节点的树，问最少添加几条边使得节点1到其他任何点的距离不超过2。
$n\le2·10^5$
BZOJ 1950 简化版

题解

  • 很显然遇到不符合的不是最优的(比如：1-2-3-4-5-6，答案是1，想不到吧)。
  • 对于所有不满足的点，假设我们现在在最底层，显然从1连它的父亲肯定可以解决它的问题修改掉它的距离，和它父亲的距离，dfs跑一次即可。
  • 需要注意每次修改完一个点，从这个点出发其他的点也要修改。
  • 怎么又被全局变量v坑了啊

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn=2e5+10;

int n, k, u, v;
vector<int>g[maxn];
int d[maxn], father[maxn], ans=0;;

void dfs(int x,int fa,int sum)
{
    father[x]=fa;
    d[x]=sum;
    for(int i=0;i<int(g[x].size());i++)
    {
        v=g[x][i];
        if(v==fa) continue;
        dfs(v, x, sum+1);
    }
}

void solve(int x,int fa)
{
    for(int i=0;i<int(g[x].size());i++)
    {
        v=g[x][i];
        if(v==fa) continue;
        int vv=v;
        d[vv]=min(d[vv], d[x]+1);
        solve(vv, x);
        d[x]=min(d[x], d[vv]+1);
    }
    if(d[x]>2)
    {
        d[x]=2;
        d[father[x]]=1;
        ans++;
    }
}

int main()
{
    scanf("%d", &n);
    for(int i=1;i<=n-1;i++){
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0, 0);
    solve(1, 0);
    printf("%d\n", ans);
}

F

题意

给两种颜色分别有数量 $a$ 和 $b$，现要求用$a+b$个颜色组成一个矩形(即矩形的面积为$a+b$)，并且至少有一种颜色$a$或$b$可以自己形成矩形，问最小周长

题解

  • 约数个数没有规律的分布，但好像都不太大的样子
  • 所以可以枚举 $a+b$ 的约数，暴力枚举a或b为矩阵的情况，判断a或b的两边是否小于等于当前$a+b$的约数即可
  • 时间复杂度$O(10^3·10^3)$左右

约数个数
结论：打表可以看出$[1,1e14]$内的数的约数个数大概也就$10^3$级别。

约数没有规律分布
质数分布：$\frac{n}{\log n}$

tokitsukaze代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <bits/stdc++.h>
using namespace std;
namespace fastIO{
	#define BUF_SIZE 100000
	#define OUT_SIZE 100000
	//fread->read
	bool IOerror=0;
//	inline char nc(){char ch=getchar();if(ch==-1)IOerror=1;return ch;} 
	inline char nc(){
		static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
		if(p1==pend){
			p1=buf;pend=buf+fread(buf,1,BUF_SIZE,stdin);
			if(pend==p1){IOerror=1;return -1;}
		}
		return *p1++;
	}
	inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
	template<class T> inline bool read(T &x){
		bool sign=0;char ch=nc();x=0;
		for(;blank(ch);ch=nc());
		if(IOerror)return false;
		if(ch=='-')sign=1,ch=nc();
		for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
		if(sign)x=-x;
		return true;
	}
	inline bool read(double &x){
		bool sign=0;char ch=nc();x=0;
		for(;blank(ch);ch=nc());
		if(IOerror)return false;
		if(ch=='-')sign=1,ch=nc();
		for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
		if(ch=='.'){
			double tmp=1; ch=nc();
			for(;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');
		}
		if(sign)x=-x;
		return true;
	}
	inline bool read(char *s){
		char ch=nc();
		for(;blank(ch);ch=nc());
		if(IOerror)return false;
		for(;!blank(ch)&&!IOerror;ch=nc())*s++=ch;
		*s=0;
		return true;
	}
	inline bool read(char &c){
		for(c=nc();blank(c);c=nc());
		if(IOerror){c=-1;return false;}
		return true; 
	}
	template<class T,class... U>bool read(T& h,U&... t){return read(h)&&read(t...);}
	#undef OUT_SIZE
	#undef BUF_SIZE
};
using namespace fastIO;
/************* debug begin *************/
string to_string(string s){return '"'+s+'"';}
string to_string(const char* s){return to_string((string)s);}
string to_string(const bool& b){return(b?"true":"false");}
template<class T>string to_string(T x){ostringstream sout;sout<<x;return sout.str();}
template<class A,class B>string to_string(pair<A,B> p){return "("+to_string(p.first)+", "+to_string(p.second)+")";}
template<class A>string to_string(const vector<A> v){
	int f=1;string res="{";for(const auto x:v){if(!f)res+= ", ";f=0;res+=to_string(x);}res+="}";
	return res;
}
void debug_out(){puts("");}
template<class T,class... U>void debug_out(const T& h,const U&... t){cout<<" "<<to_string(h);debug_out(t...);}
#ifdef tokitsukaze 
#define debug(...) cout<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__);
#else
#define debug(...) 233;
#endif
/*************  debug end  *************/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define mem(a,b) memset((a),(b),sizeof(a))
#define MP make_pair
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
using namespace __gnu_cxx;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VL;
void go();
int main(){
	#ifdef tokitsukaze
		freopen("TEST.txt","r",stdin);
	#endif
	go();return 0;
}
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-6;
const int MAX=2e5+10;
const ll mod=1e9+7;
/*********************************  head  *********************************/
void go()
{
	ll a,b,i,j,sq,ans,x,y;
	while(read(a,b))
	{
		vector<PLL > res;
		sq=sqrt(a+b+0.5);
		for(i=sq;i;i--)
		{
			if((a+b)%i==0) res.pb(MP(i,(a+b)/i));
		}
		ans=LLINF;
		sq=sqrt(a+0.5);
		for(i=1;i<=sq;i++)
		{
			if(a%i==0)
			{
				x=i;
				y=a/i;
				for(j=0;j<sz(res);j++)
				{
					if(x<=res[j].fi&&y<=res[j].se) ans=min(ans,2*(res[j].fi+res[j].se));
				}
			}
		}
		sq=sqrt(b+0.5);
		for(i=1;i<=sq;i++)
		{
			if(b%i==0)
			{
				x=i;
				y=b/i;
				for(j=0;j<sz(res);j++)
				{
					if(x<=res[j].fi&&y<=res[j].se) ans=min(ans,2*(res[j].fi+res[j].se));
				}
			}
		}
		printf("%lld\n",ans);
	}
}